Firewalls and other security devices typically enforce policies against network traffic based on a set of rules. In some cases, the rules may be based on uniform resource locator (URL) information, such as by preventing a user from accessing a specific URL (e.g., denying access to http://www.example.com), or by preventing a user from accessing a category associated with the URL (e.g., denying access to URLs classified as “social networking” or “pornographic”). Unfortunately, due to factors such as the sheer number of URLs in existence, and resource constraints (e.g., on the security device), it can be difficult to efficiently match rules that make use of URL information, in particular where information about the URL is limited.